1. Field of the Invention
The present invention relates broadly to the field of telecommunications. More particularly, the present invention relates to acceptance or rejection of a proposed connection through an asynchronous transfer mode (ATM) switch or node based on available bandwidth and buffer resources at that location.
2. State of the Art
Perhaps the most awaited, and now fastest growing technology in the field of telecommunications in the 1990's is known as Asynchronous Transfer Mode (ATM) technology. ATM is providing a mechanism for removing performance limitations of local area networks (LANs) and wide area networks (WANs) and providing data transfers at a speed of on the order of gigabits/second. The variable length packets of LAN and WAN data are being replaced with ATM cells which are relatively short, fixed length packets. Because ATM cells can carry voice, video and data across a single backbone network, the ATM technology provides a unitary mechanism for high speed end-to-end telecommunications traffic.
Because the data contained in the ATM cells can be generated from either generally fixed rate communications, or bursty type communications, it will be appreciated that traffic accommodation mechanisms have been introduced in order to avoid situations where ATM switches or nodes are over-taxed, resulting in loss of cells. In particular, buffering and leaky-bucket usage regulating mechanisms are well known. In addition, it is known in the art that ATM switches and nodes will first determine whether they have the capacity to handle a proposed call before accepting the call. Such a determination is referred to as connection admission control (CAC), some details of which are standardized in ITU-T Recommendation I.371.
In constant rate communications, CAC is as simple as a summing of the data rates of all channels on a link of a switch or node, and a comparing that sum to the total throughput of that link. In variable rate communications, the situation is substantially more complex. In accord with standards, individual connections are judged by various traffic parameters, including peak cell rate (PCR), sustainable cell rate (SCR), and maximum burst size (MBS). It will be appreciated that if a connection is to be established with a guarantee of no cell loss, where buffering is limited, the peak resource demand of all connections in the switch must be added together and must not exceed the resource capacity of the switch, i.e., ##EQU1## where there are N connections through a switch, C is the link capacity and PCR. is the peak cell rate of connection i, i=1, 2, . . . , N. However, when using Equation (1) as a CAC test, the actual throughput or utilization will often be considerably lower than the capabilities of the switch, as the peak resource demand may be several times larger than the average resource demand.
To increase utilization, the effective bandwidth e.sub.i of a connection, rather than the PCR, can be used for CAC. The effective bandwidth is derived from a combination of the connection's traffic parameters (PCR, SCR, MBS), the characteristics of the link (the capacity C) and switch (space in the multiplex cell buffer B), and the quality of service specification (a maximum cell loss ratio (CLR)). Using this approach, the CAC system keeps the running total of the effective bandwidth e.sub.i values of established connections, i.e., ##EQU2## where there are N connections through a switch, C is the link capacity and e.sub.i is the effective bandwidth of connection i, i=1, 2, . . . , N. When a new connection is offered to the link, its effective bandwidth is added to the running total and the result is compared to the link capacity. If the resulting total effective bandwidth is greater than the link capacity, then the connection is rejected. If the resulting total is less than the link capacity, then the call request is accepted and included in the running total of the e.sub.i values when the next call request is received.
In order to limit the number of different calculations necessary to keep a running total of e values, it has been appreciated that the number of different e values can be limited by using connection classes. A connection class is a set of connections having similar traffic parameters; i.e., each connection class has particular values for the peak cell rate (PCR), the sustainable cell rate (SCR), and the maximum burst size (MBS). A connection is classified into the connection class which has values for the traffic parameters closest to, but not less than, the values of the parameters of the connection. An effective bandwidth e.sub.j is calculated for connection class j and the CAC test is modified as ##EQU3## where the vector K is the number of connections in class j.
It has been further appreciated that where there are numerous connections through a switch, it is statistically likely that the peak cell rate will not be reached by all connections at the same time. Thus, while the sum of the sustainable cell rates of all connections must be less than or equal to the available bandwidth through the switch, the sum of the peak cell rates may exceed the available resources while still meeting a targeted cell loss ratio (CLR) (e.g., 10.sup.-9).
This situation of maintaining numerous connections where gain is available is known in the art as a statistically-multiplexable variable bit rate (S-VBR) source situation. Conversely, however, where there are only a few connections which utilize the resources of the switch, there is more likelihood that peak cell rates will be reached by all connections at the same time. Thus, in these circumstances, gain cannot be achieved, and the sum of the peak resource utilization should not exceed the available resources if desirable cell loss ratios are to be met. This situation is known in the art as a nonstatistically-multiplexable variable bit rate (NS-VBR) source situation.
In a paper entitled "A New Approach for Allocating Buffers and Bandwidth to Heterogeneous Regulated Traffic in an ATM Node", IEEE-JSAC-13 #6, pp.1115-1127 (1995) by A. Elwalid et al., which is hereby incorporated by reference herein in its entirety, the concept of statistically-multiplexable and nonstatistically-multiplexable VBR traffic types are quantified. Classification into the NS-VBR and S-VBR source types is done by calculating the critical capacity required in order to statistically multiplex connections with given traffic parameters. If the link capacity C is greater than the critical capacity of the link, then the connection type is S-VBR. Otherwise, the connection type is NS-VBR.
In the Elwalid et al. paper, the concept of the effective bandwidth is utilized to quantify the minimum amount of bandwidth allocated to a connection in order to achieve a zero-cell loss ratio, i.e., a "zero-loss effective bandwidth" e.sub.0. In particular, it is shown that for a connection having known PCR, SCR, and MBS values, and given a particular link capacity (C) and buffer size (B), a zero-loss effective bandwidth e.sub.0 can be determined.
It is also shown that a "single class effective bandwidth" e can be computed. This is the minimum amount of bandwidth a connection should be allocated to achieve a given non-zero cell loss ratio when a number of identical but statistically independent connections are multiplexed onto a link. A value for e can be computed from the connection parameters SCR, PCR, and MBS, the multiplexer parameters B and C, and the target cell loss ratio L.
Different connections having the same connection parameters can be grouped together as a connection class. A boundary region defines the maximum number of connections from each of the classes depending upon the number of connections from the other of the classes. If the number of connection classes to be multiplexed together is J, then a J-dimensional "state space" may be defined with the coordinate system {K.sub.j : j=1, . . . , J} where K.sub.j is the number of connections in class j present in the "multiplex" or mix of connections. Each point in the state space represents a unique mix of connections. The "admissible region" is the set of all points in state space for which the resulting loss ratio is no greater than the target L. The admissible region is a contiguous volume of state space adjacent to the origin bounded by the "admissible region boundary" (and the constraints that K.sub.j .gtoreq.0).
The admissible region boundary touches the axes of the state space at K.sub.j =C/e.sub.j for each class j=1, . . . , J. For S-VBR connections, SCR.ltoreq.e&lt;e.sub.0 .ltoreq.PCR. For NS-VBR connections, SCR.ltoreq.e=e.sub.0 .ltoreq.PCR.
Where only two classes of connections are present and both are NS-VBR, the acceptance region is bounded by a straight line as seen in prior art FIG. 1. Where two classes of connections of S-VBR sources are present, the acceptance region is bounded by a slightly curved line as seen in prior art FIG. 2. Using complex equations described in the Elwalid et al. paper, the slightly curved line can be conservatively approximated by a straight line.
The Elwalid et al. paper further analytically deals with the situation where classes from different connection types (S-VBR and NS-VBR) are present. In such situations the boundary of admissible sets is non-linear with a straight line portion and a curved portion. The entire boundary curve cannot be approximated by a straight line. However, according to Elwalid et al., the curved portion of the non-linear boundary may, in many cases be approximated by a straight line which is tangent to an intermediate point of the curve. A representation of the acceptance region boundary associated with a multiple connection type situation is seen in prior art FIG. 3, with the dotted line T representing a line tangent to the curve.
While the Elwalid et al. paper is very useful in quantifying the boundary curves and lines and thus in theory providing a determination of whether calls proposed for a switch can be properly handled by the switch, application of theory set forth in Elwalid et al. to ATM switches is not straight-forward. In particular, the calculations required to generate the acceptance curve are extremely complex, and are not feasibly conducted in real time at the switch. In addition, each time a proposed call is received, it must be reviewed in order to determine whether its acceptance would cause movement out of the acceptance region.